package agorithm.week1.classOne;


import agorithm.bean.ListNode;

/**
 * 25. K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * @author zcc
 * @date 2021/06/17/18:35
 */
public class ReverseList {
    public static void main(String[] args) {
        ListNode node1 = ListNode.getNode();
        ListNode p = reverseKGroup(node1, 2);
        System.out.println("max = " + p);
    }


    /**
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode preNode = new ListNode(0, null);
        // 上一个节点
        ListNode pre = preNode;
        while (head != null) {
            // 获取区间尾节点
            ListNode endNode = getEndNode(head, k);
            if (endNode == null) {
                break;
            }
            // 下一个节点
            ListNode next = endNode.next;
            // 区间反转链表
            reverseList(head, endNode);
            // 前节点关联指向区间节点的尾节点(反转后的头节点)
            pre.next = endNode;
            // pre指向区间的头节点即下一次循环的头节点
            pre = head;
            // 下一个循环的头节点
            head = next;
        }
        return preNode.next;
    }

    public static ListNode getEndNode(ListNode head, int k) {
        ListNode curr = head;
        // --k ：k次所有点之间的链接点遍历次数。连接线比节点少一
        while (curr != null && --k != 0) {
            curr = curr.next;
        }
        return curr;
    }

    public static void reverseList(ListNode head, ListNode endNode) {
        if (head == null || head.next == null) {
            return;
        }
        // 记录endNode的下一个节点,然后跳出反转
        ListNode end = endNode.next;
        ListNode next, curr = head, pre = endNode.next;
        while (curr != null && curr != end) {
            // 记录下一个节点
            next = curr.next;
            // 指针指向pre,pre第一次为null;
            curr.next = pre;

            // 给pre赋值为当前节点；
            pre = curr;
            // 为下一次执行赋值
            curr = next;
        }
    }
}